Матч 16, Делимость (Divisibility)

Задан массив чисел a. Найти количество чисел от L до R включительно, которые делятся хотя бы на одно число массива a.

Класс: Divisibility

Метод: int numDivisible(int L, int R, vector <int> a)

Ограничения: a содержит от 1 до 18 элементов, 1 £ a[i], L, R £ 10⁹.

Вход. Два целых числа L, R и массив целых чисел a.

Выход. Количество чисел от L до R включительно, которые делятся хотя бы на одно число массива a.

Пример входа

L	R	a
293	784	{1}
255	734	{2}
1	1000000000	{2,3}

Пример выхода

492

240

666666667

РЕШЕНИЕ

комбинаторика, принцип включения - исключения

Воспользуемся фактом, что

numDivisible(L, R, a) = numDivisible(1, R, a) – numDivisible(1, L - 1, a).

Значение numDivisible(1, n, a) будем вычислять при помощи функции f(n, a). Рассмотрим процесс вычисления результата в зависимости от количества элементов в массиве a.

1. Если a содержит один элемент, то ответом будет значение n / a[0] (округление до целого производится вниз).

2. Пусть a содержит два элемента. Ответ будет меньше n / a[0] + n / a[1], так как будут существовать числа, которые делятся на a[0] и на a[1] одновременно. И в приведенной сумме такие числа будут считаться дважды. Количество чисел, делящихся одновременно на a[0] и на a[1], равно n / НОК(a[0], a[1]). Таким образом, для двух чисел

f(n, a) = n / a[0] + n / a[1] – n / НОК(a[0], a[1])

3. Пусть a содержит три элемента. Тогда согласно принципу включения – исключения

f(n, a) = n / a[0] + n / a[1] + n / a[2] –

– n / НОК(a[0], a[1]) – n / НОК(a[1], a[2]) – n / НОК(a[0], a[2]) + n / НОК(a[0], a[1], a[2])

Поскольку по условию задачи массив a содержит от 1 до 18 элементов, то перебрать все подмножества множества a можно не более чем за 2¹⁸ операций. При этом если подмножество содержит нечетное число элементов, то значение n / НОК() следует прибавлять к накапливаемой сумме (ответу), если четное – то вычитать.

Если при вычислении НОК() текущее значение НОК() станет больше n для некоторого j < k, то процесс вычисления НОК() можно завершить, так как тогда n / НОК() = 0.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

int gcd(int a, int b)

{

return (!b) ? a : gcd(b,a % b);

}

int f(int N, vector<int> &a)

{

int i, j, bits, temp, res = 0, n = (int)a.size();

long long lcm;

for(i = 1; i < (1<<n); i++)

{

lcm = 1; bits = 0;

for(j = 0; j < n; j++)

if (i & (1 << j))

{

bits++;

temp = gcd(lcm,a[j]);

lcm = lcm / temp * a[j];

if (lcm > N) break;

}

if (bits % 2) res += N / lcm; else res -= N / lcm;

}

return res;

}

class Divisibility

{

public:

int numDivisible(int l, int r, vector<int> a)

{

return f(r,a) - f(l - 1,a);

}

};